#
# @lc app=leetcode.cn id=35 lang=python
#
# [35] 搜索插入位置
#

# @lc code=start
class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 直接遍历，O(n)
        for i in range(len(nums)):
            if nums[i] < target:
                continue
            else:
                return i
        return len(nums)


class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if nums[0] > target:
            return 0
        if nums[len(nums)-1] < target:
            return len(nums)

        i, j = 0, len(nums)-1
        while i < j:
            k = int((i+j)/2)
            if nums[k] < target:
                i = k + 1
            elif nums[k] == target:
                return k
            else:
                j = k - 1
        if nums[i] < target:
            return i+1
        else:
            return i


        

# @lc code=end

if __name__ == "__main__":
    solution = Solution()
    result = solution.searchInsert([1, 3, 5, 6], 2)
    print(result)